/*
 * @Description: 牛客左神--排序算法
 * @Author: Wel_Come
 * @Date: 2019-08-14 16:59:38
 * @LastEditTime: 2019-08-19 16:29:34
 * @LastEditors: Please set LastEditors
 */


/**
 * @description:  冒泡排序
 * @param {array} arr 需要进行排序的数组
 * @return: array 排序好的数组
 */ 
const bubbleSort = function(arr){
    const len = arr.length
    for(let i=0;i<len-1 ;i++){
        for(let j=0;j<len-i;j++){
            console.log(i,j,arr[j] , arr[j+1])
            if(arr[j] > arr[j+1]){
                [arr[j],arr[j+1]] = [arr[j+1],arr[j]]
            }
        }
    }
    return arr
}
 



/**
 * @description: 选择排序
 * @param {array} arr 
 * @return: array 排序好的数组
 */
const selectSort = function(arr){
    var minIndex

    for(let i=0;i<arr.length;i++){
        minIndex = i
        for(let j = i+1;j<arr.length;j++){
             if(arr[minIndex]>arr[j]){
                 minIndex = j
             }
        }
        [arr[i],arr[minIndex]] = [arr[minIndex],arr[i]]
    }
    return arr
}


/**
 * @description: 插入排序
 * @param {array} arr 
 * @return: array 排序好的数组
 */
const insertSort = function(arr){
    const len = arr.length
    for(let i=1;i<len;i++){
        var j = i-1
        while(arr[j+1]<arr[j] && j>=0){
            [arr[j+1],arr[j]] = [arr[j],arr[j+1]]
            j--
        }
    }
    return arr
}


/**
 * @description: 归并排序
 * @param {array} arr 需要被排序的数组
 * @return: array 排序好的数组
 */

 const mergeSort = function(arr){
    /**
     * @description:数组对半分离方法， 
     * @param {arrat} arr  需要被排序的数组
     * @return: 最终排序好的数组
     */
    const separate = function(arr){
        if(arr.length < 2) return arr
        const middleIndex = Math.floor(arr.length/2)
        const left = arr.slice(0,middleIndex)
        const right = arr.slice(middleIndex)
        return merge(separate(left),separate(right))
    }

    /**
     * @description: 每一个小部分的排序
     * @param {array} left 左部分数组
     * @param {array} right 右部分数组
     * @return: 合并好的数组
     */
    const merge = function(left,right){
        const result = []
        while(left.length && right.length){
            result.push( left[0]>right[0] ? left.shift() : right.shift() )
        }
        
        result.push(...left,...right)
        return result
    }

    // 调用函数
    return separate(arr)
 }





/**
 * @description: 快速排序
 * @param {array} 需要被排序的数组
 * @return: array 合并好的数组
 */ 
const quickSort = function(arr){
    if(arr.length < 2) return arr
    const middleIndex = Math.floor(arr.length/2)
    const middleItem = arr.splice(middleIndex,1)[0]
    
    let left = []
    let right = []
    arr.forEach(item=>{
        middleItem>item ? left.push(item) : right.push(item)
    })

    return quickSort(left).concat([middleItem],quickSort(right))
}


/**
 * @description: 堆排序
 * 堆就是个完全二叉树，数量为n的二叉树，高度为Math.floor(logN)+1
 *  在二叉树里面，2I+1是左边分支，2I+2是右 边分支  I为层数
 * @param {type} 
 * @return: 
 */
